(This problem is an interactive problem.)
A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.
Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.
You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:
BinaryMatrix.get(row, col)returns the element of the matrix at index(row, col)(0-indexed).BinaryMatrix.dimensions()returns the dimensions of the matrix as a list of 2 elements[rows, cols], which means the matrix isrows x cols.
Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
For custom testing purposes, the input will be the entire binary matrix mat. You will not have access to the binary matrix directly.
Example 1:
Input: mat = [[0,0],[1,1]] Output: 0
Example 2:
Input: mat = [[0,0],[0,1]] Output: 1
Example 3:
Input: mat = [[0,0],[0,0]] Output: -1
Example 4:
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]] Output: 1
Constraints:
rows == mat.lengthcols == mat[i].length1 <= rows, cols <= 100mat[i][j]is either0or1.mat[i]is sorted in non-decreasing order.
Average Rating: 4.96 (73 votes)
Solution
Approach 1: Linear Search Each Row
Intuition
This approach won't pass, but we'll use it as a starting point. Also, it might be helpful to you if you just needed an example of how to use the API, but don't want to see a complete solution yet!
The leftmost 1 is the 1 with the lowest column index.
The problem can be broken down into finding the index of the first 1 in each row and then taking the minimum of those indexes.
The simplest way of doing this would be a linear search on each row.
Algorithm
Complexity Analysis
If you ran this code, you would have gotten the following error.
You made too many calls to BinaryMatrix.get().
The maximum grid size is 100 by 100, so it would contain 10000 cells. In the worst case, the linear search algorithm we implemented has to check every cell. With the problem description telling us that we can only make up to 1000 API calls, this clearly isn't going to work.
Let N be the number of rows, and M be the number of columns.
-
Time complexity : O(N⋅M)
We don't know the time complexity of
binaryMatrix.get()as its implementation isn't our concern. Therefore, we can assume it's O(1).In the worst case, we are retrieving a value for each of the N⋅M cells. At O(1) per operation, this gives a total of O(N⋅M).
-
Space complexity : O(1).
We are only using constant extra space.
Approach 2: Binary Search Each Row
Intuition
This isn't the best approach, but it passes, and coding it up is a good opportunity to practice binary search.
When linear search is too slow, we should try to find a way to use binary search. If you're not familiar with binary search, check out this Explore Card!. We recommend doing the first couple of binary search questions to get familiar with the algorithm before coming back to this problem.
Also, have a go at First Bad Version. The only difference between that problem and this one is that instead of 0 and 1, it uses false and true.
Like we did with the linear search, we're going to apply binary search independently on each row. The target element we're searching for is the first 1 in the row.
The core part of a binary search algorithm is how it decides whether the target element is to the left or the right of the middle element. Let's figure this out by thinking through a couple of examples.
In the row below, we've determined that the middle element is a 0. On what side must the target element (first 1) be? The left, or the right? Don't forget, all the 0's are before all the 1's.
In this next row, the middle element is a 1? What side must the target element be on? Could it also possibly be the 1 we just found?
For the first example, we can conclude that the target element (if it exists) must be to the right of the middle element. This is because we know that everything to the left of a 0 must also be a 0,
For the second example, we can conclude that the target element is either the middle element itself or it is some other 1 to the left of the middle element. We know that everything to the right of a 1 is also a 1, but these can't possibly be further left than the one we just found.
In summary, if the middle element is a:
- 0, then the target must be to the right.
- 1, then the target is either this element or to the left.
We can then put this together into an algorithm that finds the index of the target element (first 1) in each row, and then returns the minimum of those indexes. Here is an animation of how that algorithm would look. The light grey numbers are the ones that we could infer without needing to make an API call. They are only there to help you understand.
Algorithm
If you're already quite familiar with binary search, feel free to skip down to the implementation below. I've decided to include lots of details here, as binary search is one of those algorithms that a lot of people get frustrated with easily and find it difficult to master.
In a binary search, we always keep track of the range that the target might be in by using two variables: lo to represent the lowest possible index it could be, and hi to represent the highest possible index it could be. Ignoring the binaryMatrix API details for the moment, here is a rough outline of our binary search in pseudocode.
define function binary_search(input_list):
lo = the lowest possible index
hi = the highest possible index
while the search space contains 2 or more items:
mid = the middle index in the remaining search space
if the element at input_list[mid] is 0:
lo = mid + 1 (the first 1 is *further right*, and can't be mid itself)
else:
hi = mid (the first 1 is either mid itself, *or is further left*)
return the only index remaining in the search space
As always in binary search, there are a couple more key implementation details we still need to deal with:
- An even-length search space has two middles. Which do we choose?
- The row might be all 0's.
Let's tackle these issues one at a time.
The first issue, the choice of middle, is important, as otherwise, the search space might stop shrinking when it gets down to two elements. When the search space doesn't shrink, the algorithm does the exact same thing the next loop cycle, resulting in an infinite loop. Remember that when the search space only contains two elements, they are the ones pointed to by lo and hi. This means that the lower middle equals lo, and the upper-middle equals hi. We, therefore, need to think about which cases would shrink the search space, and which would not.
If we use the lower-middle
- If it is a
0, then we setlo = mid + 1. Becausehi == mid + 1, this means thatlo == hi(search space is of length-one). - If it is a
1, then we sethi = mid. Becausemid == lo, this means thathi == lo(search space is of length-one).
If we use the upper-middle
- If it is a
0, then we setlo = mid + 1. Becausehi = mid, we now havehi > lo(search space is of length-zero). - If it is a
1, then we sethi = mid. Becausehi == midwas already true, the search space stays as is (of length-two).
If we use the lower-middle, we know the search space will always shrink. If we use the upper-middle, it might not. Therefore, we should go with the lower-middle. The formula for this is mid = (low + high) / 2.
The second issue, a row of all zeroes, is solved by recognizing that the algorithm always shrinks down the search space to a single element. This is supposed to be the first 1, but if that doesn't exist, then it has to be a 0. Therefore, we can detect this case by checking whether or not the last element in the search space is a 1.
It is good practice to think these details through carefully so that you can write your binary search algorithm decisively and confidently. Resist the urge to Program by Permutation!
Anyway, putting this all together, we get the following code.
Complexity Analysis
Let N be the number of rows, and M be the number of columns.
-
Time complexity : O(NlogM).
There are M items in each row. Therefore, each binary search will have a cost of O(logM). We are performing N of these binary searches, giving a time complexity of N⋅O(logM)=O(NlogM).
-
Space complexity : O(1).
We are using constant extra space.
Approach 3: Start at Top Right, Move Only Left and Down
Intuition
Did you notice in Approach 2 that we didn't need to finish searching all the rows? One example of this was row 3 on the example in the animation. At the point shown in the image below, it was clear that row 3 could not possibly be better than the minimum we'd found so far.
Therefore, an optimization we could have made was to keep track of the minimum index so far, and then abort the search on any rows where we have discovered a 0 at, or to the right of, that minimum index.
We can do even better than that; on each search, we can set hi = smallest_index - 1, where smallest_index is the smallest index of a 1 we've seen so far. In most cases, this is a substantial improvement. It works because we're only interested in finding 1s at lower indexes than we previously found. Here is an animation of the above example with this optimized algorithm. The algorithm eliminates as many cells as it can with each API call. It also starts by checking the last cell of the row before proceeding with the binary search, to eliminate needless binary searches where the row only had 0s left in it.
Here is what the worst-case looks like. Like before, its time complexity is still O(MlogN).
While this is no worse than Approach 2, there is a better algorithm.
Start in the top right corner, and if the current value is a
0, move down. If it is a1, then move left.
The easiest way to see why this works is an example. Here is an animation of it.
You probably gained some intuitive sense as to why this works, just from watching the animation.
- When we encounter a
0, we know that the leftmost1can't be to the left of it. - When we encounter a
1, we should continue the search on that row (move pointer to the left), in order to find an even smaller index.
Algorithm
Complexity Analysis
Let N be the number of rows, and M be the number of columns.
-
Time complexity : O(N+M).
At each step, we're moving 1 step left or 1 step down. Therefore, we'll always finish looking at either one of the M rows or N columns. Therefore, we'll stay in the grid for at most N+M steps, and therefore get a time complexity of O(N+M).
-
Space complexity : O(1).
We are using constant extra space.
May 27, 2020 12:25 PM
O(M+N) can be worse than O(NlogM) if M is much large than N.
Last Edit: September 21, 2020 6:58 AM
One of the optimization that I thought of when I saw the problem was the fact that each row is sorted (or is non-decreasing). So we can prune candidate rows just by looking at the last column of each row. If the last column is 1, then that means, we can binary search this row, on the other hand, if the last row is 0, then there is no point in searching this row.
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
rows, cols = binaryMatrix.dimensions()
min_col = float("inf")
def get_left_most(row_id: int) -> int: # returns the earliest 1
start, end = 0, cols
while start < end:
mid = start + (end-start)//2
if binaryMatrix.get(row_id, mid) == 1:
end = mid
else:
if mid > min_col:
return float("inf") # no point in searching to the
# right of already low soln
start = mid + 1
return start
for i in range(rows):
if binaryMatrix.get(i, cols-1) == 1: # candidate row
first_1 = get_left_most(i)
min_col = min(min_col, first_1)
return min_col if min_col != inf else -1
November 2, 2020 12:42 AM
This is one of the best binary search space explanations.
Last Edit: April 22, 2020 5:28 PM
Python 3 code to illustrate the first part of the Approach 3, complexity O(MlogN).
Bisect left each row up to the current best answer.
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
mat = binaryMatrix
R, C = mat.dimensions()
ans = C
for r in range(R):
idx = self.bisect_left(mat, r, ans)
ans = min(ans, idx)
return -1 if ans == C else ans
def bisect_left(self, mat, r, hi):
lo = 0
while lo < hi:
mi = lo + (hi-lo)//2
if mat.get(r, mi):
hi = mi
else:
lo = mi + 1
return hi
April 21, 2020 8:02 PM
As mentioned before guess we can combine approach 2 and 3 for better results!
Last Edit: February 5, 2021 5:30 AM
why do they use the word "non-decreasing order." they can just say increasing order... Am I missing something here?
April 27, 2021 1:02 AM
We don't have to binary Search for entire row. We can keep track of where we found the 1 in the above row, and that can be used as right boundary for next row.
Last Edit: February 22, 2021 12:23 AM
binary search can be greatly optimized. You can check if low is greater or equal to your currently found smallest index. If that's the case, you can break out of the binary search for that row since any index it may possibly return cannot be less than what you've already seen
from math import inf
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
# def get(self, row: int, col: int) -> int:
# def dimensions(self) -> list[]:
class Solution:
def searchRow(self, matrix, row_index, row_len, min_found):
low = 0
high = row_len - 1
while low <= high and low < min_found:
mid = (low + high) // 2
if matrix.get(row_index, mid) == 0:
low = mid + 1
else:
min_found = min(min_found, mid)
high = mid - 1
return min_found
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
num_rows, num_cols = binaryMatrix.dimensions()
min_found = inf
for i in range(num_rows):
min_found = min(min_found, self.searchRow(binaryMatrix, i, num_cols, min_found))
if min_found == inf:
return -1
return min_found
April 15, 2021 10:13 PM
So are the columns sorted? Is this matrix proper?
[ 1 1 ]
[ 0 1 ]
?
Either the description of the problem is wrong, or the solution is wrong - solution assumes both rows and columns are sorted. Description explains that only rows are sorted.
January 10, 2021 1:13 PM
We can combine solution 2 and solution 3: every time we go down to the next row, we use binary search to find the target 1 instead of a trivial linear search
You don't have any submissions yet.
xxxxxxxxxx/** * // This is the BinaryMatrix's API interface. * // You should not implement it, or speculate about its implementation * class BinaryMatrix { * public: * int get(int row, int col); * vector<int> dimensions(); * }; */class Solution {public: int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) { }};